// 优先级队列
// 数组中每次都需要拿到最大元素或者最小元素，可以考虑用堆的思想解决
// top K 问题要想到用堆解决

// 例题 2：
// 设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
//
//        请实现 KthLargest 类：
//
//        KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
//        int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
//
//        示例 1：
//
//        输入：
//        ["KthLargest", "add", "add", "add", "add", "add"]
//        [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
//
//        输出：[null, 4, 5, 5, 8, 8]
//
//        解释：
//
//        KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
//        kthLargest.add(3); // 返回 4
//        kthLargest.add(5); // 返回 5
//        kthLargest.add(10); // 返回 5
//        kthLargest.add(9); // 返回 8
//        kthLargest.add(4); // 返回 8
//
//
//        示例 2：
//
//        输入：
//        ["KthLargest", "add", "add", "add", "add"]
//        [[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]
//
//        输出：[null, 7, 7, 7, 8]
//
//        解释：
//
//        KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);
//        kthLargest.add(2); // 返回 7
//        kthLargest.add(10); // 返回 7
//        kthLargest.add(9); // 返回 7
//        kthLargest.add(9); // 返回 8
//
//
//        提示：
//        0 <= nums.length <= 104
//        1 <= k <= nums.length + 1
//        -104 <= nums[i] <= 104
//        -104 <= val <= 104
//        最多调用 add 方法 104 次

// 解题思路：
// 建立小根堆，依次让元素入队
// 当堆的数量超过 k ，让堆顶元素出队
// 堆顶元素就是第 k 大元素

import java.util.PriorityQueue;

public class KthLargest {
    PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> a - b);
    int n = 0;
    public KthLargest(int k, int[] nums) {
        n = k;
        for(int i = 0; i < nums.length; i++){
            heap.offer(nums[i]);
            if(heap.size() > k) heap.poll();
        }
    }

    public int add(int val) {
        heap.offer(val);
        if(heap.size() > n) heap.poll();
        return heap.peek();
    }
}
